/**
 * Created by L.jp
 * Description:给定单链表的头节点head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
 *
 * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为偶数 ，以此类推。
 *
 * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
 *
 * 你必须在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。

 * User: 86189
 * Date: 2022-02-12
 * Time: 22:13
 */
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
public class Soluition {
    /*  对于原始链表，每个节点都是奇数节点或偶数节点。头节点是奇数节点，头节点的后一个节点是偶数节点，相邻节点
的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表，然后将偶数链表连接在奇数链表之后，
合并后的链表即为结果链表。
      原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点，head 的后一个节点是偶数链表的头节点。
令 evenHead = head.next，则 evenHead 是偶数链表的头节点。

维护两个指针 odd 和 even 分别指向奇数节点和偶数节点，初始时 odd = head，even = evenHead。通过迭代的方
式将奇数节点和偶数节点分离成两个链表，每一步首先更新奇数节点，然后更新偶数节点。
更新奇数节点时，奇数节点的后一个节点需要指向偶数节点的后一个节点，因此令 odd.next = even.next，然
后令 odd = odd.next，此时 odd 变成 even 的后一个节点。
更新偶数节点时，偶数节点的后一个节点需要指向奇数节点的后一个节点，因此令 even.next = odd.next，然
后令 even = even.next，此时 even 变成 odd 的后一个节点。
    * */

    //怎么分离链表其实就是断开相邻的指向，分成奇偶两个链表，其实就是重新连线的题目，分离完奇偶链表之后再把奇链表的尾接在偶链表的头就可以了

    public ListNode oddEvenList(ListNode head) {
        if(head == null)
            return null;
        ListNode odd=head;//奇链表的头，搜索奇链表
        ListNode evenHead=head.next;//偶链表的头
        ListNode even=evenHead;//搜索偶链表
        while(even != null && even.next != null){
            //找奇索引节点，就是偶索引节点的下一个节点
            odd.next = even.next;//连接奇链表
            odd=odd.next;//继续找
            //找偶索引节点，就是当前奇索引节点的下一个节点
            even.next = odd.next;
            even = even.next;//继续找
        }
        //偶索引在前面，偶索引走完了，那么奇索引肯定也走完了，之后连接奇偶链表
        odd.next=evenHead;//奇尾连偶头
        return  head;
    }
}
